The present invention relates to a variable length code decoding system having a cache memory.
First, a modified Huffman code (simply called a xe2x80x9cMH codexe2x80x9d hereinafter) will be described briefly. A MH code system is to convert, in connection with a while/black binary image, the number of continuous pixels of the same color (white or black) (called a xe2x80x9crun lengthxe2x80x9d) into the MH code.
In the MH code, two series of codes are used which include a terminate code as shown in FIG. 9 and a makeup code as shown in FIG. 10, corresponding to the run length of the while or black. In this code, the run length is represented by a quotient and a remainder obtained when the run length is divided by 64. The makeup code corresponds to the quotient, and the remainder corresponds to the terminate code. Accordingly, assuming that the quotient is represented by M and the remainder is represented by T, the run length RL is expressed as follows:
RL=Mxc3x9764+T
Therefore, the terminate code corresponds to the run length of xe2x80x9c0xe2x80x9d to xe2x80x9c63xe2x80x9d, and the makeup code corresponds to the run length which is a multiple of 64 and which reaches 2560 at maximum.
For example, in the case of a white/black binary image as shown in FIG. 6, first, three white pixels continues, and the run length becomes 3. Referring to the while run code of the run length xe2x80x9c3xe2x80x9d in the terminate code table of the MH code in FIG. 9, the code of xe2x80x9c1000xe2x80x9d can be obtained. Accordingly, the run length in the range of xe2x80x9c0xe2x80x9d pixel to 63 pixels can be coded by on the terminate code.
As regards the run length of not less than 64 pixels, the run length is coded by first using the makeup code table shown in FIG. 10. The makeup code is followed by the terminate code indicating a difference between an actual run length and the run length represented by the makeup code (See the code corresponding to the run length of xe2x80x9cWHITE 130xe2x80x9d FIG. 6.
Incidentally, the coding of a line head is started with a while run. If an actual line head is a black run, the while run of the run length xe2x80x9c0xe2x80x9d is coded.
Next, the feature of the MH code will be described. The MH code is constituted by the format that is shown FIG. 7. As shown in FIG. 7, the MH code comprises 13 bits at maximum. In the bit format shown in FIG. 7, a leftmost bit is the most significant bit, and a rightmost bit is the least significant bit. The MH code is composed of a high place bit region 71 consisting of 0 bit to 7 bits, a succeeding fixed region 72 consisting of 1 bit, and a low place bit region 73 consisting of 7 bits at maximum. The values in the high place bit region 71 are xe2x80x9c0xe2x80x9d, and there is possibility that the region 71 itself does not exist. Namely, the MH code has a code sequence in which the number of continuing xe2x80x9c0xe2x80x9ds before a first xe2x80x9c1xe2x80x9d appears is seven at maximum and the number of bits succeeding to the first xe2x80x9c1xe2x80x9d is also seven at maximum.
For example, when the three white pixels continue as shown in FIG. 6, it is coded to a four-bit MH code which does not include the region 71 and which the region 72 of xe2x80x9c1xe2x80x9d and the region 73 of xe2x80x9c000xe2x80x9d. When 130 white pixels continue as shown in FIG. 6, it is coded to an MH code having no region 71 and the region 72 of xe2x80x9c1xe2x80x9d and the region 73 of xe2x80x9c0010xe2x80x9d, which is followed by an MH code having the region 71 of only one xe2x80x9c0xe2x80x9d, the region 72 of xe2x80x9c1xe2x80x9d and the region 73 of xe2x80x9c11xe2x80x9d outputted in the named order. The MH code is transferred serially from the most significant bit in order.
Now, a conventional MH code decoding system will be described. The decoding of the MH code is to convert the serially transferred and inputted MH code into the run length. This conversion is conventionally carried out by referring to a decoding conversion table stored in a ROM (read only memory).
Since the MH code is 13 bits at maximum, the conventional MH code decoding system is configured to carry out the decode by supplying a 14-bit address obtained by adding one bit of a white/black information to the MH code, to an address of the decoding conversion ROM, and by obtaining information of 11 bits in total, including 6 bits of the run length, four bits of the code length, and one bit indicative of which of the terminate code and the makeup code it is.
For example, the MH code decoding system disclosed by Japanese Patent Application Post-examination Publication No. JP-B-02-002350, is configured to decode as follows in order to reduce the capacity of the ROM. This decoding system utilizes the feature in which, in the serially transferred and inputted MH code sequence, the number of continuing xe2x80x9c0xe2x80x9ds before the first xe2x80x9c1xe2x80x9d appears is seven at maximum and the number of bits succeeding to the first xe2x80x9c1xe2x80x9d is also seven at maximum. An address of 11 bits comprising 3 bits indicative of the number of continuing xe2x80x9c0xe2x80x9ds before the first xe2x80x9c1xe2x80x9d appears, 7 bits succeeding to the first xe2x80x9c1xe2x80x9d, and one bit indicative of a while/black information, is supplied as an address of the decoding conversion ROM. Information of 10 bits in total comprising 6 bits of the run length, 3 bits indicative of the number of the remaining bits in the actual code, succeeding to xe2x80x9c1xe2x80x9d detected after the continuing xe2x80x9c0xe2x80x9ds, and one bit indicative of the terminate code/makeup code information. Thus, the decoding is carried out.
However, when the code data is inputted at a constant rate such as 33.6 Kbps, if the code length is relatively long, a processing time can have a margin, but if the code length is relative short, unless the processing is carried out at a high speed, the processing cannot be completed before a next code is inputted. For this purpose, a decoded data processed once is stored in a cache memory which can be read out at a speed higher than the ROM, so that when the same code pattern is inputted, the decoded data can be read out from the cache memory, without reading from a low speed ROM.
Furthermore, Japanese Patent Application Pre-examination Publication No. JP-A-09-185548 proposes a method in which decoded data corresponding to a relatively short length requiring a high speed reference, is previously transferred to a cache memory, and the cache memory is locked, so as to avoid a cache missing.
Referring to FIG. 4, there is shown a block diagram illustrating one example of the conventional MH code decoding system. In FIG. 4, a code input shift register 1 is a 8-bit shift register for bit-serially receiving a MH code sequence, and is controlled to shift leftward by a shifter 7. A zero counting circuit 3 counts the number of continuing xe2x80x9c0xe2x80x9ds (which is seven at maximum) before the first xe2x80x9c1xe2x80x9d appears in an input sequence of the shift register 1. A white/black register 2 is a one-bit register for designating the color of a white or black in the image. Here, the content of the white/black register 2 is inverted when the value of a T/M bit of an output of a control circuit 11 explained hereinafter indicates xe2x80x9cTxe2x80x9d.
A zero count register 4 holds three bits of a count output of the zero counting circuit 3. A ROM (read only memory) 5 previously stores a decoding conversion table. The ROM 5 receives, as an address input, 11 bits in total consisting of the three bits of the zero count register 4, code bits of 7 bits succeeding to the xe2x80x9c1xe2x80x9d firstly appearing in the shift register 1, and one bit of the white/black register 2 designating the color of the white or black in the image. The ROM 5 outputs 10 bits in total consisting of 6 bits indicative of the run length (RL) to be actually decoded, one bit indicative of the terminate code/makeup code (T/M) information, and three bits indicative of the number of the remaining bits in the actual code, succeeding to the xe2x80x9c1xe2x80x9d firstly appearing in the shift register 1.
A cache memory 8 can be read and written at a high speed, and receives, as an input address, the three bits of the zero count register 4 and the one bit of the white/black register 2. A comparing circuit 10 receives and compares the most significant 7 bits of the output of the shift register 1 and 7 bits of a tag value outputted from the cache memory 8. When coincidence is obtained and when a valid bit value V (valid or invalid) of one bit outputted from the cache memory 8 indicates the valid, the comparing circuit 10 outputs a control signal indicative of a cache hit. Otherwise, the comparing circuit 10 outputs a control signal indicative of a mishit.
When the control signal outputted from the comparing circuit 10 is indicative of the cache hit, the control circuit 11 selects and outputs data of 10 bits in total comprising 6 bits indicative of the run length (RL) and outputted from the cache memory 8, one bit indicative of the terminate code/makeup code (T/M) information and three bits indicative of the number of the remaining bits in the actual code, succeeding to the xe2x80x9c1xe2x80x9d firstly appearing in the shift register 1. When the control signal outputted from the comparing circuit 10 is indicative of the mishit, the control circuit 11 selects and outputs the 10-bit data from the ROM 5, and thereafter, writes the same data into the cache memory 8, registers the most significant 7 bits of the output of the shift register 1 into a tag section of the cache memory, and sets a corresponding valid bit V of the cache memory.
A selector 6 selects either the three-bit output of the zero count register 4 or the three-bit output of the control circuit 11 to output the selected one to the shifter 7. The shifter 7 adds xe2x80x9c+1xe2x80x9d to the number indicated by the three-bit input, and leftward shifts the shift register by the obtained number.
An image generating circuit 12 receives 8 bit in total including the 6 bits of the run length from the control circuit 11, the one bit from the white/black register 2 and the one bit indicative of the terminate code/makeup code (T/M) information, and generates an image of the actual run length on the basis of the received bits. An output of the image generating circuit 12 is outputted through a FIFO memory 13 as an image information.
Referring to FIG. 5, it illustrates an example of the construction of the cache memory 8 and the comparing circuit 10 in the decoding system shown in FIG. 4. The cache memory 8 comprises 16 lines, each of which is constituted of a tag, a valid bit (V), and data (run length, T/M bit, and the number of the remaining bits in the actual code, succeeding to the xe2x80x9c1xe2x80x9d firstly appearing in the MH code sequence). 4 bits in total composed of the three bits of the zero count register 4 and the one bit of the white/black register 2, constitute an index for selecting the line. Code bits of the 7 bits succeeding to the xe2x80x9c1xe2x80x9d firstly appearing in the shift register 1 become a tag, which is associated with a valid bit (V) of one bit indicating whether the data in each line is valid or invalid.
The comparing circuit 10 comprises a comparator 101 and a logical AND gate 102. The comparator 101 compares the 7 bits succeeding to the xe2x80x9c1xe2x80x9d firstly appearing in the shift register 1 with the 7 bits of the tag value outputted from the cache memory 8, and outputs a control signal indicative of a line hit when coincidence is obtained. The AND gate 102 executes a logical AND between the value of the control signal outputted from the comparator 101 and the value of the valid bit (V) (one bit) outputted from the cache memory 8. Thus, the AND gate 102 outputs a control signal indicative of a cache hit only when the control signal outputted from the comparator 101 is indicative of the line hit, and when the valid bit value (V) is indicative of the valid. Otherwise, the AND gate 102 outputs a control signal indicative of a mishit
Next, an operation of the above mentioned decoding system will be described. In FIG. 4, first 8 bits of a serially transferred MH code sequence are inputted and held in a shift register I. The number of xe2x80x9c0xe2x80x9ds from the leftmost bit position of the shift register 1 before the xe2x80x9c1xe2x80x9d firstly appearing in the shift register, is counted by use of the zero counting circuit 3, and the obtained value is stored in the zero count register 4. The value stored in the zero count register 4 is selected by the selector 6 and supplied to the shifter 7.
This shifter 7 leftward shifts the content of the shift register 1 by the value obtained by adding xe2x80x9c+1xe2x80x9d to the received value, and succeeding bits are inputted and held in the shift register by the number of bits which was leftward shifted. With this operation, code bits of 7 bits at maximum, succeeding to the xe2x80x9c1xe2x80x9d firstly appearing in the shift register, are held in the shift register 1. Thus, as shown in FIG. 8A, the code bits of 7 bits succeeding to the xe2x80x9c1xe2x80x9d firstly appearing in the shift register, the one bit outputted from the white/black register 2, and the value (3 bits) of the zero count register 4, are supplied as an address to the ROM 5. And, as shown in FIG. 8B, the ROM 5 outputs 10 bits in total including the 6 bits indicative of the run length, the one bit (T/M) indicative of the terminate code/makeup code information, and the three bits indicative of the number of the remaining bits in the actual code, succeeding to the xe2x80x9c1xe2x80x9d firstly appearing in the shift register 1.
On the other hand, four bits in total composed of the 3 bits of the output of the zero count register 4 and the one bit of the white/black register 2, are supplied as an address to the cache memory 8.
As shown in FIG. 5, in the cache memory 8, the line is selected by using, as an index, the four bits in total composed of the 3 bits of the zero count register 4 and the one bit of the white/black-register 2. The cache memory 8 outputs the 7 bits of the tag of the selected line, one bit of the valid bit value of the selected line and 10 bits of the data (run length, T/M bit, and the number of the remaining bits in the actual code, succeeding to the xe2x80x9c1xe2x80x9d firstly appearing in the MH code sequence). The tag of the selected line is supplied to the comparator 101, which compares with the 7 bits of the tag outputted from the cache memory with the 7 bits succeeding to the xe2x80x9c1xe2x80x9d firstly appearing in the shift register 1, and outputs the control signal indicative of the line hit when coincidence is obtained. The AND gate 102 receives the control signal of the comparator 101 and the valid value (V) of the selected line in the cache memory 8, and outputs the result of the execution of the logical AND. Thus, only when the control signal outputted from the comparator 101 is indicative of the line hit and the valid bit value (V) is indicative of the valid, the AND gate 102 outputs the control signal indicative of a cache hit. Otherwise, the AND gate 102 outputs the control signal indicative of a mishit
Returning to FIG. 4, when the control signal outputted from the comparing circuit 10 is indicative of the cache hit, the control circuit 11 selects and outputs the 10 bits in total outputted from the cache memory 8, including the 6 bits indicative of the run length (RL), the one bit (T/M) indicative of the terminate code/makeup code information, and the three bits indicative of the number of the remaining bits in the actual code, succeeding to the xe2x80x9c1xe2x80x9d firstly appearing in the shift register 1. When the control signal outputted from the comparing circuit 10 is indicative of the mishit, the control circuit 11 selects and outputs the 10-bit data outputted from the ROM 5.
Succeedingly, the control circuit 11 writes the 10-bit data outputted from the ROM 5, into the line in the cache memory designated by the four bits in total composed of the 3 bits of the zero count register 4 and the one bit of the white/black register 2. Furthermore, the control circuit 11 registers the most significant 7 bits of the output of the shift register 1, to the tag of the selected line, and sets the valid bit (V) of the selected line. These values registered and set in the cache memory are used at a next and succeeding accesses to the cache memory 8.
Of the 10-bit data outputted from the control circuit 11 (RL, T/M, and the number of the remaining bits in the actual code, succeeding to the firstly appeared xe2x80x9c1xe2x80x9d), the run length of 6 bits and the T/M bit of one bit are supplied in parallel together with one bit of the white/black register 2, to the image generating circuit 12. This data is restored into a image signal by the image generating circuit 12, and the restored image signal is serially supplied to the FIFO memory 13. Here, when the value of the T/M bit indicates M (makeup code), the value of the run length is multiplied by 64. On the other hand, when the value of the T/M bit indicates T (terminate code), the value of the run length is outputted as it is and the content of the while/black register is inverted.
Furthermore, the bits indicative of the number of the remaining bits in the actual code, succeeding to the firstly appeared xe2x80x9c1xe2x80x9d, are outputted from the control circuit, and are selected by the selector 6 to be supplied to the shifter 7. The number of the remaining bits in the actual code, succeeding to the firstly appeared xe2x80x9c1xe2x80x9d, becomes information which determine a heading position of a code to be next decoded. Namely, the shifter 7 leftward shifts the content of the shift register 1 by the number of the remaining bits in the actual code, succeeding to the firstly appeared xe2x80x9c1xe2x80x9d, and new code bits are inputted into the shift register 1 by the shifted number. Thus, the code to be next decoded is set in the shift register. The above mentioned operation is repeated for the decoding until the code becomes not inputted.
In the above mentioned conventional MH code decoding system, since the cache memory is accessed by using a portion of the variable length code as an address input, there is a waste in a data storage of the cache memory, and therefore, the hit rate of the cache memory 8 is low.
For example, in the decoding system shown in FIG. 4, when the xe2x80x9cblack 16xe2x80x9d (code=xe2x80x9c0000010111xe2x80x9d) is decoded, the value of the zero count register 4 is xe2x80x9c101xe2x80x9d (=5), the value of the white/black register 2 is xe2x80x9c1xe2x80x9d indicative of black, and the code of the 7 bits succeeding to the firstly appeared xe2x80x9c1xe2x80x9d, is xe2x80x9c0111XXX (where xe2x80x9cXXXxe2x80x9d is a portion of a next code succeeding to the code of the xe2x80x9cblack 16xe2x80x9d in the code sequence).
Therefore, the address (index) supplied to the cache memory 8 is xe2x80x9c1011xe2x80x9d, since it is composed of four bits in total including the three bits of the zero count register 4 and the one bit of the while/black register 2. Since the tag is the code of the 7 bits succeeding to the firstly appeared xe2x80x9c1xe2x80x9d, it become xe2x80x9c0111XXXxe2x80x9d. In this case, since this is a heading one of the code sequence, the cache memory 8 is mishit, and the data (run length, T/M bit, and the number of the remaining bits in the actual code, succeeding to the firstly appeared xe2x80x9c1xe2x80x9d) is read out from the ROM 5. This data is stored in a data storing region of the xe2x80x9c1011xe2x80x9dth line in the cache memory 8. Simultaneously, xe2x80x9c0111XXXxe2x80x9d is stored in the tag of the xe2x80x9c1011xe2x80x9dth line, and the valid bit (V) of the xe2x80x9c1011xe2x80x9dth line is set.
In succeeding accesses, when the code of the xe2x80x9cblack 16xe2x80x9d is inputted, xe2x80x9c1011xe2x80x9d is supplied to the cache memory 8 as an address (index), and the stored xe2x80x9c0111XXXxe2x80x9d is outputted as the tag value. However, since the code succeeding to the second xe2x80x9cblack 16xe2x80x9d is not necessarily the same as the code succeeding to the first xe2x80x9cblack 16xe2x80x9d, the code of the 7 bits succeeding to the firstly appeared xe2x80x9c1xe2x80x9d stored in the shift register 1 is xe2x80x9c0111YYYxe2x80x9d (where xe2x80x9cYYYxe2x80x9d is a portion of a next code succeeding to the code of the second xe2x80x9cblack 16xe2x80x9d in the code sequence). Therefore, xe2x80x9cXXXxe2x80x9d is not necessarily equal to xe2x80x9cYYYxe2x80x9d.
Accordingly, the data inputted from the shift register 1 to the comparing circuit 10 is xe2x80x9c0111YYYxe2x80x9d, which is not necessarily equal to xe2x80x9c0111XXXxe2x80x9d of the tag value supplied from the cache memory 8. As a result, although the decoded data of the xe2x80x9cblack 16xe2x80x9d exists in the cache memory 8, the cache is mishit and therefore the cache is not necessarily hit.
As mentioned above, in the conventional decoding system for the variable length code such as the MH code, whether the cache is hit or mishit is judged by discriminating whether or not the portion of the variable length code as an address input to the cache memory, is coincident with the tag stored in the cache memory. In this case, however, when the variable length code is inputted, it is not clear where the code terminates. Therefore, when the code has a length shorter than a maximum code length, data that is not included in the actual code to be decoded (namely, a portion of the code succeeding to the actual code to be decoded) becomes a portion of the input address. On the other hand, the tag value stored in the cache memory includes data that was not included in the actual code decoded (namely, a portion of the code that succeeded to the actual code decoded). Therefore, since two data portions not included in the actual code do not necessarily become the same, a portion of the input address of the cache memory and the tag stored in the cache memory are not often coincident with each other, with the result that the cache is mishit.
Therefore, a problem is encountered in which although the decoded data exists in the cache memory, the cache is mishit, and therefore, the hit rate of the cache memory is low.
As proposed in Japanese Patent Application Pre-examination Publication No. JP-A-09-185548, in the case that some number of items of decoded data corresponding to a relatively short code length are previously transferred to a cache memory, and the cache memory is locked so as to avoid a cache missing, it is possible to reduce the mishit of the cache memory attributable to the fact that no data to be referred exists in the cache memory. However, there still exists the above mentioned problem in which although the decoded data exists in the cache memory, the cache is mishit.
Accordingly, it is an object of the present invention to provide a variable length code decoding system having a cache memory, which has overcome the above mentioned problem of the prior art.
Another object of the present invention is to provide a variable length code decoding system having a cache memory, capable of effectively storing data in the cache memory to elevate the hit rate of the cache memory.
The above and other objects of the present invention are achieved in accordance with the present invention by a variable length code decoding system having a cache memory and so configured to execute a decoding by accessing the cache memory by using a variable length code as an address, the system comprising a hit/mishit discriminating means for discriminating whether or not the cache is hit, by comparing the address with a tag read out from the cache memory in only a limited range corresponding to an effective code length of the variable length code.
In an embodiment of the variable length code decoding system, the hit/mishit discriminating means includes a mask circuit and a comparing circuit. The mask circuit receives code bits of 7 bits succeeding to a firstly appeared xe2x80x9c1xe2x80x9d in a modified Huffman code sequence, a tag value of 7 bits outputted from the cache memory, and the number of remaining bits in an actual code, succeeding to the firstly appeared xe2x80x9c1xe2x80x9d, which is a portion of data outputted from the cache memory. The mask circuit outputs the code bits of 7 bits succeeding to the firstly appeared xe2x80x9c1xe2x80x9d and having bits which are other than the remaining bits in the actual code and which are masked by the mask circuit, and the tag value of the 7 bits outputted from the cache memory and having bits which are other than the remaining bits in the actual code and which are masked by the mask circuit.
The comparing circuit receives and compares the code bits of 7 bits having the bits masked by the mask circuit and the tag value of the 7 bits having the bits masked by the mask circuit, so that the comparing circuit outputs a control signal indicative of a cache hit only when coincidence is obtained in the comparison and a valid bit outputted from the cache memory is indicative of valid. The comparing circuit otherwise outputs a control signal indicative of a mishit.
Specifically, the mask circuit includes a mask value generating circuit and first and second logical AND circuits. The mask value generating circuit receives the number of remaining bits in the actual code, succeeding to the firstly appeared xe2x80x9c1xe2x80x9d, and outputs a mask value of 7 bits for masking the bits which are other than the remaining bits in the actual code. The first logical AND circuit receives the mask value of 7 bits and the tag value of the 7 bits outputted from the cache memory, for outputting the tag value of the 7 bits having the bits which are other than the remaining bits in the actual code and which are masked by the mask circuit. The second logical AND circuit receives the mask value of 7 bits and the code bits of 7 bits succeeding to the firstly appeared xe2x80x9c1xe2x80x9d in the modified Huffman code sequence, for outputting the code bits of 7 bits having the bits which are other than the remaining bits in the actual code and which are masked by the mask circuit.
In addition, the comparing circuit includes a comparator and a logical AND gate. The comparator compares the code bits of 7 bits having the bits masked by the mask circuit and the tag value of the 7 bits having the bits masked by the mask circuit, for outputting a control signal indicative of a line hit when coincidence is obtained. The logical AND gate receives the control signal from the comparator and the valid bit outputted from the cache memory, for outputting the control signal indicative of the cache hit only when the control signal from the comparator is indicative of the line hit and the valid bit is indicative of the valid. The logical AND gate otherwise outputs the control signal indicative of the mishit.
In another embodiment of the variable length code decoding system, the cache memory includes a plurality of cache memories, and the hit/mishit discriminating means includes a mask circuit and a comparing circuit provided for each of the plurality of cache memories.
Each mask circuit receives code bits of 7 bits succeeding to a firstly appeared xe2x80x9c1xe2x80x9d in a modified Huffman code sequence, a tag value of 7 bits outputted from a corresponding cache memory, and the number of remaining bits in an actual code, succeeding to the firstly appeared xe2x80x9c1xe2x80x9d, which is a portion of data outputted from the corresponding cache memory. Each mask circuit outputs the code bits of 7 bits having bits which are other than the remaining bits in the actual code and which are masked by the mask circuit, and the tag value of the 7 bits having bits which are other than the remaining bits in the actual code and which are masked by the mask circuit.
Each comparing circuit receives and compares the code bits of 7 bits having the bits masked by the corresponding mask circuit and the tag value of the 7 bits having the bits masked by the corresponding circuit, each comparing circuit outputting a control signal indicative of a cache hit only when coincidence is obtained in the comparison and a valid bit outputted from the corresponding cache memory is indicative of valid. The comparing circuit otherwise outputs a control signal indicative of a mishit.
The system further includes:
a control circuit;
a shift register receiving the modified Huffman code sequence;
a zero detecting means for detecting the number of continuing xe2x80x9c0xe2x80x9ds, which is seven at maximum, before the firstly appeared xe2x80x9c1xe2x80x9d appears in the modified Huffman code sequence, the zero detecting means outputting three bits indicative of the number of continuing xe2x80x9c0xe2x80x9ds thus detected;
a decoding conversion ROM receiving, as an address input, 11 bits in total comprising the three bits indicative of the number of continuing xe2x80x9c0xe2x80x9ds, the code bits of 7 bits succeeding to the firstly appeared xe2x80x9c1xe2x80x9d, and one bit indicative of a color of white or black of an image to be decoded, the decoding conversion ROM outputting 10 bits in total comprising 6 bits indicative of the run length to be actually decoded, one bit indicative of which of a terminate code and a makeup code the code under decoding is, and the three bits indicative of the number of remaining bits in the actual code, succeeding to the firstly appeared xe2x80x9c1xe2x80x9d;
a discriminating circuit receiving the control signal from each comparing circuit, the discriminating circuit outputting to the control circuit, a second control signal indicative of a cache hit when any of the comparing circuits outputs the first mentioned control signal indicative of the cache hit and a discriminating signal indicative of which of the plurality of cache memories is hit, the discriminating circuit outputting the second control signal indicative of a mishit to the control circuit when none of the comparing circuits outputs the first mentioned control signal indicative of the cache hit;
a first selector receiving the discriminating signal for selecting, among 10-bit data respectively outputted from the plurality of cache memories, the 10-bit data outputted from a hit cache memory in accordance with the discriminating signal, the first selector outputting the selected 10-bit data;
a selecting circuit receiving a valid bit outputted from each of the plurality of cache memories, the selecting circuit outputting a selection control signal for selecting a cache memory outputting the valid bit indicative of invalid when any of the received valid bits is indicative of invalid, the selecting circuit outputting the selection control signal for forcibly selecting any of the plurality of cache memories when all of the received valid bits are indicative of valid; and
a second selector receiving the selection control signal for selecting one of the plurality of cache memories in accordance with the selection control signal,
so that when the second control signal outputted from the discriminating circuit indicates the mishit, the control circuit selects the 10-bit data from the decoding conversion ROM, and outputs the selected 10-bit data to the second selector, and the selected 10-bit data is written through the second selector into the cache memory selected by the second selector at a line of the selected cache memory designated by four bits in total including the three bits outputted from the zero detecting means and the one bit indicative of the color of white or black, most significant 7 bits of an output of the shift register being registered into a tag of the line written with the selected 10-bit data, and the valid bit in the line written with the selected 10-bit data being set,
whereby these values are used in a next and succeeding accesses to the cache memories.
With the above mentioned arrangement, when the decoding is carried out by accessing the cache memory by using a variable length code as an address, whether the cache memory is hit or mishit is judged by discriminating whether or not the code bits of the 7 bits succeeding to the firstly appeared xe2x80x9c1xe2x80x9d in the actual code are coincident with the tag stored in the cache memory. Here, this comparison is carried out by masking bits other than an effective bit length of the actual code, by utilizing the three-bit information indicating the number of remaining bit in the actual code, succeeding to the firstly appeared xe2x80x9c1xe2x80x9d, outputted from the cache memory. Thus, the hit rate of the cache memory can be elevated.
The above and other objects, features and advantages of the present invention will be apparent from the following description of preferred embodiments of the invention with reference to the accompanying drawings.